/**
找到该树中两个指定节点的最近公共祖先
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 */
import arrayToTree from './0-数组转为二叉树.js'
var lowestCommonAncestor = function(root, p, q) {
  if(!root) return null
  if(root.val===p || root.val===q) return root.val // 如果当前节点是p或q，则返回当前节点
  const left  = lowestCommonAncestor(root.left,p,q)
  const right = lowestCommonAncestor(root.right,p,q)
  if(left&&right) { // 如果左右子树都找到了，则当前节点就是最近公共祖先
    return root.val
  }
  else if(left) return left // 如果左子树找到了，则返回左子树
  else if(right) return right // 如果右子树找到了，则返回右子树
};
const root = [3,5,1,6,2,0,8,null,null,7,4]
const p = 5
const q = 4
console.log(lowestCommonAncestor(arrayToTree(root),p,q))

// var lowestCommonAncestor = function(root, p, q) {
//   if(!root) return null
//   if(root===p || root === q) return root
//   const left  = lowestCommonAncestor(root.left,p,q)
//   const right = lowestCommonAncestor(root.right,p,q)
//   if(left&&right) {
//     return root
//   }
//   else if(left) return left
//   else if(right) return right
// };